package com.shiguiwu.springmybatis.algorithm.sort;

import cn.hutool.core.util.RandomUtil;

import java.util.Arrays;

/**
 * @description: 排序测试
 * @author: stone
 * @date: Created by 2021/3/15 22:37
 * @version: 1.0.0
 * @pakeage: com.shiguiwu.springmybatis.algorithm.sort
 */
public class SortTests {

    public static void main(String[] args) {

        Sort proxy = null;
        int[] array = init(80000);
        int[] temp = Arrays.copyOf(array, array.length);
        int[] temp1 = Arrays.copyOf(array, array.length);
        int[] temp2 = Arrays.copyOf(array, array.length);
        int[] temp3 = Arrays.copyOf(array, array.length);
        int[] temp4 = Arrays.copyOf(array, array.length);
        int[] temp5 = Arrays.copyOf(array, array.length);
//        System.out.println(Arrays.toString(array));
        Sort bubble = new BubbleSort(array);
        Sort select = new SelectSort(temp);
        Sort insertSort = new InsertSort(temp1);
        Sort shellSort = new ShellSort(temp2);
        Sort quickSort = new QuickSort(temp3);
        Sort mergeSort = new MergeSort(temp4);
        Sort radixSort = new RadixSort(temp5);
//        bubbl.sort();
        proxy = UseTimeSortProxy.createProxy(bubble, Sort.class);
        //冒泡排序 8w数据14s
        proxy.sort();
//        System.out.println(Arrays.toString(array));

        proxy = UseTimeSortProxy.createProxy(select, Sort.class);
        //选择排序
        proxy.sort();
//        System.out.println(Arrays.toString(temp));

        proxy = UseTimeSortProxy.createProxy(insertSort, Sort.class);
        //插入排序
        proxy.sort();

        proxy = UseTimeSortProxy.createProxy(shellSort, Sort.class);
        //希尔排序
        proxy.sort();


        proxy = UseTimeSortProxy.createProxy(quickSort, Sort.class);
        //快速排序
        proxy.sort();


        proxy = UseTimeSortProxy.createProxy(mergeSort, Sort.class);
        //归并排序
        proxy.sort();

        //todo 负数情况
        proxy = UseTimeSortProxy.createProxy(radixSort, Sort.class);
        //基数排序
        proxy.sort();
    }

    public static int[] init(int size) {
        int[] array = new int[size];
        for (int i = 0; i < size; i++) {
            array[i] = RandomUtil.randomInt(0, size);
        }
        return array;
    }

    //并归排序

    public static void split(int[] arr, int left, int right, int[] temps) {
        if (left >= right) {
            return;
        }

        int min = (left + right) / 2;

        split(arr,left,min,temps);

        split(arr, min + 1, right, temps);

        //合并，利用栈的机制，重最后执行的方法开始
        merge(arr, left, min, right, temps);

    }

    public static void merge(int[] arr, int left, int min, int right, int[] temps) {


        int i = left;
        int j = min + 1;

        int index = 0;
        while (i <= min && j <= right) {

            if (arr[i] <= arr[j]) {
                temps[index] = arr[i];
                i++;
            }
            else {
                temps[index] = arr[j];
                j++;
            }
            index++;
        }


        //左边剩余
        while (i <= min) {
            temps[index] = arr[i];
            index++;
            i++;
        }

        //右边剩余
        while (j <= right) {
            temps[index] = arr[j];
            index++;
            j++;
        }



        //拷贝
        int left1 = left;
        index = 0;

        while (left1 <= right) {
            arr[left1] = temps[index];
            index ++;
            left1++;
        }
    }


    //选择排序，寻找最
    public static void sort1(int[] arr) {

        int min;
        int minIndex;
        for (int i = 0; i < arr.length; i++) {
            min = arr[i];
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (min > arr[j]) {
                    min = arr[j];
                    minIndex = j;
                }
            }


            if (minIndex != i) {
                arr[minIndex] = arr[i];
                arr[i] =min;

            }
        }

    }
}
